package com.caoyanan.algorithm.question.zuoTraining.training004.class03;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 给定一棵二叉树的头节点head，和一个数K
 * 路径的定义:
 * 可以从任何一个点开始，但是只能往下走，往下可以走到任何节点停止
 * 返回路径累加和为K的所有路径中，最长的路径最多有几个节点？
 * @author: caoyanan
 * @time: 2021/6/16 0:30
 */
public class Question01_BinaryTreeMaxNodePath {

    public static class Node {
        int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    public static void main(String[] args) {

        //                   3
        //           -2             3
        //        1      4      5      -7
        //       3 5   2 -5  -5  -3   1   5
        int K = 0;
        Node head = new Node(3);
        head.left = new Node(-2);
        head.left.left = new Node(1);
        head.left.right = new Node(4);
        head.left.left.left = new Node(3);
        head.left.left.right = new Node(5);
        head.left.right.left = new Node(2);
        head.left.right.right = new Node(5);

        head.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(-7);
        head.right.left.left = new Node(-5);
        head.right.left.right = new Node(-3);
        head.right.right.left = new Node(1);
        head.right.right.right = new Node(5);

        System.out.println(maxNodePath(head, K));
    }

    /**
     * 这道题和一个数组求子数组和小于等于K的最大子数组和为多少是一样的模型
     * 那道题是构建一个前缀和数组，枚举以i位置结尾前缀和是 sum，找  大于等于 (sum - K) 的最小前缀和，
     * 然后 (sum - 这个最小前缀和) 就是 以i位置结尾的 子数组和小于等于K的最大子数组
     * 注意，这个前缀和数组中应该加一个0，比如 {5}, 10, 这时候应该返回5，
     * 如果前缀和数组没有那个0，当来到0位置的时候，前缀和是5， 找 大于等于 5-10=-5的最小前缀和，
     * 前缀和是空，没找到。以0位置结束的子数组没有小于等于K的子数组和。而实际是有的， {5} 就是
     * 所以，默认是有一个前缀和为0的可以认为是-1位置的前缀和。
     * 真正的找不到应该是比如 {10}, k=5，找 大于等于10-5=5的最小前缀和，前缀和数组只有一个0，没有大于等于5的，所以找不到。正常的找不到应该是这种情况
     *
     * 这个题目也是类似的，准备一个路径前缀和数组
     * @param head
     * @param k
     * @return
     */
    private static int maxNodePath(Node head, int k) {

        Map<Integer, Integer> sumAndLevelMap = new HashMap<>();
        sumAndLevelMap.put(0, 0);
        AtomicInteger answer = new AtomicInteger(-1);
        process(head, 1, 0, k, sumAndLevelMap, answer);
        return answer.get();
    }

    private static void process(
            Node node, int level, int preSum, int k,
            Map<Integer, Integer> sumAndLevelMap, AtomicInteger answer) {

        if (Objects.isNull(node)) {
            return;
        }
        int value = node.value;
        int sum = preSum + value;
        if (!sumAndLevelMap.containsKey(sum)) {
            sumAndLevelMap.put(sum, level);
        }
        Integer beginLevel = sumAndLevelMap.get(k - value);
        if (Objects.nonNull(beginLevel)) {
            answer.set(Math.max(answer.get(), level - beginLevel + 1));
        }
        process(node.left, level + 1, sum, k, sumAndLevelMap, answer);
        process(node.right, level + 1, sum, k, sumAndLevelMap, answer);

        // 恢复现场
        if (sumAndLevelMap.get(sum) == level) {
            sumAndLevelMap.remove(sum);
        }
    }
}
